# A bloody large number.
INFINITY = float('inf')
from FakeGameState import FakeGameState
import BlokusGameConstants as C


class TimeOut(Exception):
    pass


class AlphaBetaSearch:
    '''
    This search algorithm implements the limited-resource minimax tree search
    algorithm with alpha-beta pruning for zero-sum games. This version cuts off
    search by depth alone and uses an evaluation function (utility).
    '''

    def __init__(self, player, utility, noMoreTime=lambda: False):
        '''
        Constructor.

        @param player: Your player. This search algorithm will choose the best
                       actions for this player.
        @param utility: An evaluation function for states.
        '''
        self.player = player
        self.utility = utility
        self.noMoreTime = noMoreTime

    def search(self, maxDepth, currentState, orderfunc):
        '''
        Search game to determine best action; use alpha-beta pruning.

        @param maxDepth: The depth of the search tree.
        @param currentState: The current game state to start the search from.
        '''
        self.maxDepth = maxDepth

        bestAction = None
        bestValue = -INFINITY
        self.orderfunc = orderfunc
        valueFunction = self.__minValue if currentState.getCurrentPlayer() == self.player else self.__maxValue
        for action, state in FakeGameState(currentState).get_successors(orderfunc):
            if bestAction is None:
                bestAction = action
            try:
                value = valueFunction(state, bestValue, INFINITY, 1)
            except TimeOut:
                break
            if value > bestValue:
                bestValue = value
                bestAction = action

        return (bestAction, bestValue)

    def __edgeValue(self, state, alpha, beta, depth, value, func, test, valueFunction):
        if self.noMoreTime():
            raise TimeOut()
        if depth >= self.maxDepth or state.is_win():
            return self.utility(state)

        for _, successor in state.get_successors(self.orderfunc):
            tempVal = valueFunction(successor, alpha, beta, depth + 1)
            value = func(value, tempVal)
            if test(value, alpha, beta):
                break
            alpha = func(alpha, value)

        return value

    def __maxValue(self, state, alpha, beta, depth):
        return self.__edgeValue(state, alpha, beta, depth,
                                -INFINITY, max, lambda v, a, b: v >= b, self.__minValue)

    def __minValue(self, state, alpha, beta, depth):
        return self.__edgeValue(state, alpha, beta, depth,
                                INFINITY, min, lambda v, a, b: v <= a, self.__maxValue)
